2022년04월02일 2번
[과목 구분 없음] 정렬 알고리즘 중 최악의 경우를 가정할 때 시간복잡도가 다른 것은?
- ① 삽입 정렬(Insertion sort)
- ② 쉘 정렬(Shell sort)
- ③ 버블 정렬(Bubble sort)
- ④ 힙 정렬(Heap sort)
(정답률: 71%)
문제 해설
힙 정렬은 최악의 경우에도 시간복잡도가 O(nlogn)으로 일정하다. 이는 힙 정렬이 힙이라는 자료구조를 이용하여 정렬하기 때문인데, 힙은 항상 높이가 logn 이하인 완전 이진 트리이기 때문에 삽입, 삭제, 탐색 등의 연산이 모두 O(logn)에 이루어지기 때문이다. 따라서 입력 데이터의 크기에 상관없이 일정한 시간복잡도를 보장할 수 있다. 반면, 삽입 정렬, 쉘 정렬, 버블 정렬은 최악의 경우에는 O(n^2)의 시간복잡도를 가지므로 입력 데이터의 크기가 커질수록 성능이 급격히 저하될 수 있다.
